/*
 * Hash.c
 *
 *  Created on: 2011-7-8
 *      Author: gexiao
 */
/*
 * Hash table. The dominant calls are add and lookup, with removals
 * happening very infrequently. We use probing, and don't worry much
 * about tombstone removal.
 */
#include "Dalvik.h"

#include <stdlib.h>
#include <assert.h>

//table load factor, i.e. how full can it get before we resize
#define LOAD_NUMER 5 //62.5%
#define LOAD_DENOM 8

/*
 * Create and initialize a hash table.
 */
HashTable* dvmHashTableCreate(size_t initialSize, HashFreeFunc freeFunc) {
	HashTable* pHashTable;

	assert(initialSize > 0);

	pHashTable = (HashTable*) malloc(sizeof(*pHashTable));

	if (pHashTable == NULL)
		return NULL;

	dvmInitMutex(&pHashTable->lock);

	pHashTable->tableSize = dexRoundUpPower2(initialSize);
	pHashTable->numEntries = pHashTable->numDeadEntries = 0;
	pHashTable->freeFunc = freeFunc;
	pHashTable->pEntries = (HashEntry*) malloc(
			pHashTable->tableSize * sizeof(HashEntry));

	if (pHashTable->pEntries == NULL) {
		free(pHashTable);
		return NULL;
	}
	memset(pHashTable->pEntries,0,pHashTable->tableSize*sizeof(HashEntry));
	return pHashTable;
}

/*
 * Resize a hash table. We do this when adding an entry increased the
 * size of the table beyond its comfy limit.
 *
 * This essentially requires re-inserting all elements into the new storage.
 *
 * If multiple threads can access the hash table, the table's lock should
 * have been grabbed before issuing the "lookup+add" call that led to the
 * resize, so we don't have a synchronization problem here.
 */
static bool resizeHash(HashTable* pHashTable, int newSize) {
	HashEntry* pNewEntries;
	int i;

	//may have some code here

	pNewEntries = (HashEntry*) calloc(newSize, sizeof(HashEntry));
	if (pNewEntries == NULL)
		return false;

	for (i = 0; i < pHashTable->tableSize; i++) {
		void* data = pHashTable->pEntries[i].data;
		if (data != NULL && data != HASH_TOMBSTONE) {
			int hashValue = pHashTable->pEntries[i].hashValue;
			int newIdx;

			//probe for new spot, wrapping around
			newIdx = hashValue & (newSize - 1);
			while (pNewEntries[newIdx].data != NULL)
				newIdx = (newIdx + 1) & (newSize - 1);

			pNewEntries[newIdx].hashValue = hashValue;
			pNewEntries[newIdx].data = data;
		}
	}

	free(pHashTable->pEntries);
	pHashTable->pEntries = pNewEntries;
	pHashTable->tableSize = newSize;
	pHashTable->numDeadEntries = 0;

	//may have some code here.
	return true;
}

/*
 * Look up an entry.
 *
 * We probe on collisions, wrapping around the table.
 */
void* dvmHashTableLookup(HashTable* pHashTable, u4 itemHash, void* item,
		HashCompareFunc cmpFunc, bool doAdd) {
	HashEntry* pEntry;
	HashEntry* pEnd;
	void* result = NULL;

	assert(pHashTable->tableSize > 0);
	assert(item != HASH_TOMBSTONE);
	assert(item != NULL);

	//jump to the first entry and probe for a match
	pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize - 1)];
	pEnd = &pHashTable->pEntries[pHashTable->tableSize];
	while (pEntry->data != NULL) {
		if (pEntry->data != HASH_TOMBSTONE && pEntry->hashValue == itemHash
				&& (*cmpFunc)(pEntry->data, item) == 0) {
			//match
			break;
		}
		pEntry++;
		if (pEntry == pEnd) { //wrap around to start
			if (pHashTable->tableSize == 1)
				break; //edge case - single-entry table
			pEntry = pHashTable->pEntries;
		}
	}

	if (pEntry->data == NULL) {
		if (doAdd) {
			pEntry->hashValue = itemHash;
			pEntry->data = item;
			pHashTable->numEntries++;

			/*
			 * We'be added an entry. See if this brings us too close to full.
			 */
			if ((pHashTable->numEntries + pHashTable->numDeadEntries)
					* LOAD_DENOM > pHashTable->tableSize * LOAD_NUMER) {
				if (!resizeHash(pHashTable, pHashTable->tableSize * 2)) {
					//don't really have a way to indicate failure
					dvmAbort();
				} else {
					//for debug
				}

				//full table is bad -- search for nonexistent never halts
				assert(pHashTable->numEntries < pHashTable->tableSize);
				result = item;
			}
		} else {
			assert(result == NULL);
		}
	} else {
		result = pEntry->data;
	}

	return result;
}

/*
 * Remove an entry from the table.
 *
 * Does NOT invoke the "free" function on the item.
 */bool dvmHashTableRemove(HashTable* pHashTable, u4 itemHash, void* item) {
	HashEntry* pEntry;
	HashEntry* pEnd;

	assert(pHashTable->tableSize>0);

	//jump to the first entry and probe for a match
	pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize - 1)];
	pEnd = &pHashTable->pEntries[pHashTable->tableSize];
	while (pEntry->data != NULL) {
		if (pEntry->data == item) {
			pEntry->data = HASH_TOMBSTONE;
			pHashTable->numEntries--;
			pHashTable->numDeadEntries++;
			return true;
		}

		pEntry++;
		if (pEntry == pEnd) { //wrap around to start
			if (pHashTable->tableSize == 1)
				break;//edge case - single-entry table
			pEntry = pHashTable->pEntries;
		}
	}

	return false;
}

